package com.leetcode.offer.chapter4;


import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Dennis Li
 * @date 2020/7/13 21:19
 */
public class VerifyPostorder_33 {


    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    //  递归方式，判断每一个子树都满足BST的性质
    private boolean recur(int[] post, int i, int j) {
        if (i >= j) return true;
        int p = i;
        // 找到第一个大于p的节点 --- p之前的都是root的左子树
        while (post[p] < post[j]) p++;
        // 记录此时的左子树顶点
        int m = p;
        // 找到第一个等于p的节点 --- 找右子树部分
        while (post[p] > post[j]) p++;
        // 如果最后的p与j相等，代表找到了相应的顶点
        return p == j && recur(post, i, m - 1) && recur(post, m, j - 1);
    }

    // 单调栈：单调栈与单调队列很相似。首先栈是后进先出的，单调性指的是严格的递增或者递减。
    // 注意遍历的顺序是 根 -> 右 -> 左： 当左子树入栈后，会发生树的向下遍历。
    // 由于是反序 -- 右子树部分会比较靠前，能够保证对于整棵树进行遍历
    public boolean verifyPostorder2(int[] post) {
        Deque<Integer> stack = new LinkedList<>();
        int root = Integer.MAX_VALUE;
        for (int i = post.length - 1; i >= 0; i--) {
            if (post[i] > root) return false;
            // 与上面的思路相同，当碰到右子树部分
            while (!stack.isEmpty() &&
                    // 因为按照BST的性质，从右到左
                    stack.peek() > post[i]) // 保证栈的单调性
                // 碰到较小的，说明产生了向下的遍历，根节点发生了变换
                root = stack.pop();
            stack.push(post[i]);
        }
        return true;
    }

    public boolean verifyPostorder3(int[] post) {
        Deque<Integer> stack = new LinkedList<>();
        int root = Integer.MAX_VALUE;
        for (int i = post.length - 1; i >= 0; i--) {
            // 遍历两层才会执行替换
            // 单增的节点一定是在栈中的，且root没有更新
            // 如果发现更大的，那么说明不是BST
            if(post[i] > root) return false;
            while(!stack.isEmpty() && stack.peek() > post[i])
                root = stack.pop();
            stack.push(post[i]);
        }
        return true;
    }

}
